1. Field of the Invention
The invention relates to an associative memory array and more particularly, to a method for retrieving a constant value associated with a particular key using a unified regular expression.
2. Description of the Related Art
An associative memory array comprises a plurality of key-value pairs in which each key is associated with one constant value. A key-value lookup is an operation of retrieving the constant value associated with a particular key. This operation can be performed by software systems operating under a variety of programming languages (e.g., C++, Perl, Java, etc.). Generally, two different data structures represent associative arrays: hash tables and binary tress. In either data structure, upon receiving a query, the lookup operation matches the query exactly to a particular key and then extracts the associated constant value. Typically, keys are fixed in that they contain no restrictions, exceptions, alternatives or qualifications (e.g., keys can be represented by a fixed number, word, phrase, etc.). Therefore, the query must match exactly with a particular key to retrieve the associated constant value. Requiring keys to be fixed makes using associative memory arrays for large scale systems impractical. Additionally, to identify a match typically each query must be evaluated against each of the keys in the associative array until a match is found. Requiring each key to be evaluated separately against the query until a match is found can be time-consuming and, thus, costly and inefficient. Therefore, there is a need for a method of retrieving constant values (i.e., performing a lookup operation) for keys that are not fixed (i.e., keys that may have restrictions, exceptions, alternatives, or qualifications) and for retrieving constant values more efficiently.